package com.hy.prefix_add;

import java.util.ArrayList;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:1177. 构建回文串检测
 * <p>
 * User:Mr.Du
 * Date:2024/5/20
 * Time:9:32
 */
public class CanMakePaliQueries {

    /**
     * 判断给定字符串的子字符串是否可以经过重新排列变为回文串。
     *
     * @param s 给定的字符串。
     * @param queries 一个二维数组，每个子数组代表一个查询，包含三个整数[left, right, k]。
     *                表示查询从索引left到right的子字符串，是否可以通过最多改变k个字符变为回文串。
     * @return 返回一个布尔值列表，对应每个查询的结果：如果可以经过重新排列变为回文串，则列表中对应位置为true，否则为false。
     */
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int n = s.length();
        int[][] sum = new int[n + 1][26]; // 使用前缀和数组sum，sum[i][j]表示从索引0到i的子字符串中字母j出现的次数。
        // 计算前缀和。
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i].clone();
            sum[i + 1][s.charAt(i) - 'a']++;
        }

        List<Boolean> ans = new ArrayList<Boolean>(queries.length); // 预分配空间，存储查询结果。
        // 遍历所有查询。
        for (int[] q : queries) {
            int left = q[0], right = q[1], k = q[2], m = 0;
            // 计算[left, right]子字符串中奇数出现次数的总和。
            for (int j = 0; j < 26; j++)
                m += (sum[right + 1][j] - sum[left][j]) % 2;
            // 判断是否可以通过最多改变k个字符变为回文串。
            ans.add(m / 2 <= k);
        }
        return ans;
    }

    public List<Boolean> canMakePaliQueries1(String s, int[][] queries) {

        List<Boolean> ans = new ArrayList<>();
        int index = 0;
        for(int i = 0;i < queries.length;i++){
            ans.add(isPar(s, queries[i][0], queries[i][1], queries[i][2]));
        }
        return ans;
    }

    /**
     * @param s 输入的字符串
     * @param left 字符串中开始检查的索引
     * @param right 字符串中结束检查的索引
     * @param k 需要成对的字符数量的下限
     */
    public boolean isPar(String s, int left, int right, int k){
        // 初始化一个长度为26的数组，用于计数每个字母的出现次数
        int[] nums = new int[26];

        // 统计字符串中[left, right]范围内每个字符的出现次数
        while(left <= right){
            nums[s.charAt(left) - 'a']++;
            left++;
        }

        // 计算出现次数为奇数的字符的数量
        int count = 0;
        for(int i : nums){
            if(i % 2 != 0){
                count++;
            }
        }

        // 判断是否至少存在k个成对的字符（即k个奇数次字符的对数）
        return k >= count / 2;
    }
}
